#include <cstdio>
#include <cstring>

#define MAXN 100+5
#define INF 0x3F3F3F3F
#define MIN(a,b) (a>b?b:a)

int G[MAXN][MAXN];
int N, M;
int dis[MAXN][MAXN];

void input() {
	memset(G, 0x3F, sizeof(G));
	for (int i=1; i<=M; i++) {
		int A, B, C;
		scanf("%d%d%d", &A, &B, &C);
		G[A][B] = C;
		G[B][A] = C;
	}
}

int floyd() {
	for (int i=1; i<=N; i++) {
		for (int j=1; j<=N; j++) {
			dis[i][j] = G[i][j];
		}
	}
	for (int k=1; k<=N; k++) {
		for (int i=1; i<=N; i++) {
			for (int j=1; j<=N; j++) {
				dis[i][j] = MIN(dis[i][j], dis[i][k]+dis[k][j]);
			}
		}
	}
	return dis[1][N];
}

int main() {
	while (true) {
		scanf("%d%d", &N, &M);
		if (N==0 && M==0) break;
		input();
		int result = floyd();
		printf("%d\n", result);
	}
	return 0;
}
